import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-06-23
 * Time: 20:43
 */
public class Test {
    //快速排序优化
    public static void quickSort( int[]arr,int left ,int right) {
        if( left >= right) {
            return ;
        }
//        if( right-left+1 <= 1000) {
//            insertSortRange( arr ,left,right);
//              return ;
//        }
        int ret = datum( arr , left ,right);
        quickSort( arr , left, ret-1);
        quickSort( arr, ret+1,right);
    }
    public static void insertSortRange( int []arr,int left,int right) {
        for(int i = left+1; i<= right;i++) {
            int tmp = arr[i];
            int j = i-1;
            for(;j>=0;j--) {
                if( arr[j] > tmp) {
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }
    //挖坑法
    public static int datum(int[]arr,int left,int right) {
        int i = left;
        int tmp = arr[left];
        while( left < right) {
            while( left < right && arr[right] >= tmp) {
               right--;
            }
            arr[left] = arr[right];
            while( left <right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
    public static void main( String []args) {
        int [] arr = new int[100000];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(1000);
        }
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
